iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0
自我挑戰組

30天 Leetcode解題之路系列 第 17

Day 17 - Remove Duplicates from Sorted List

  • 分享至 

  • xImage
  •  

大家好,我是毛毛。ヾ(´∀ ˋ)ノ
廢話不多說開始今天的解題Day~


83. Remove Duplicates from Sorted List

Question

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.


Example

Example1

Input: head = [1,1,2]
Output: [1,2]

Example2

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

解題

題目

首先先簡單的翻譯一下題目
給一個排序過後的linked list,要把其中重複的節點刪除。

Think

作法大致上是這樣

  • once用來存有出現一次的值,再抓到每個節點的值的時候就進來判斷有沒有遇到過,沒有就存入。
  • 有出現過的話,就把前一個節點的next指向現在這個節點的next,就完成啦~
  • C版本的話,只差在判斷是否重複的方式不是用陣列去存,因為後來發現因為有排序過,只要存一個判斷有沒有重複就好~

Code

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        once = []
        start = head
        previous = None
        
        while start != None:
            print(start.val)
            if start.val not in once:
                once.append(start.val)
                previous = start
            else:
                previous.next = start.next

            start = start.next
            
        return head

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteDuplicates(struct ListNode* head){
    int num = -101;
    struct ListNode* start = head;
    struct ListNode* previous = 0;
    
    while (start != 0){
        // printf("%d\n", start->val);
        // printf("%d\n", start->next);
        
        if (start == head){
            num = start->val;
            previous = start;
        } else {
            if (start->val > num){
                num = start->val;
                previous = start;
            } else if (start->val == num){
                previous->next = start->next;
            }
        }
        
        start = start->next;
    }
    return head;
}

Result

  • Python

  • C

大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 16 - Reverse String
下一篇
Day 18 - Isomorphic Strings
系列文
30天 Leetcode解題之路30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言